/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-12 17:18:31
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-12 20:13:34
 * @FilePath: \LeetCode\300.最长递增子序列.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=300 lang=cpp
 *
 * [300] 最长递增子序列
 *
 * 方法1：动态规划 O(n^2)
 * - 状态 dp[i]：以第 i 个元素结尾的递增子序列长度
   dp[0] = 1
   dp[1] = dp[0] + 1 && arr[0] < arr[1]
   dp[2] = max{dp[1], dp[0]} + 1 && arr[1] < arr[2] && arr[0] < arr[2]
   ......
 * - 状态转移方程：dp[i] = max{dp[j]} + 1 && arr[j] < arr[i]
 *
 * 方法2（官方题解）：贪心 + 二分查找
 * https://leetcode.cn/problems/longest-increasing-subsequence/solutions/24173/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/?source=vscode
 * - 贪心：每次在上升子序列最后加上的那个数尽可能的小
 * - 修改 dp 一个排序列表则可以使用二分查找
 * - 状态定义：tails[k] 的值代表 长度为 k+1 子序列 的尾部元素值
 */

#include <vector>
#include <algorithm>
#include <iostream>

// @lc code=start
class Solution
{
public:
    int lengthOfLIS_01(std::vector<int> &nums)
    {
        int len = nums.size();
        int max_length = 0;
        std::vector<int> dp_LIS(len, 1);
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < i; j++)
            {
                /* dp[i] = max{1, dp[j] + 1} && arr[j] < arr[i] */
                if (nums[j] < nums[i] && (1 + dp_LIS[j]) > dp_LIS[i])
                    dp_LIS[i] = 1 + dp_LIS[j];
            }
            max_length = std::max(max_length, dp_LIS[i]);
        }

        return max_length;
    }

    int lengthOfLIS_02(std::vector<int> &nums)
    {
        std::vector<int> tails(nums.size());
        int res = 0; // 最长上升子子序列长度
        for (auto n : nums)
        {
            int i = 0, j = res;
            /* 二分确定插入位置 */
            while (i < j)
            {
                int mid = (i + j) / 2;
                if (tails[mid] < n)
                    i = mid + 1;
                else
                    j = mid;
            }
            tails[i] = n;
            if (j == res) 
                res++;
        }
        return res;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {7, 7, 7, 7, 7, 7};
    // std::cout << solution.lengthOfLIS(nums) << std::endl;
    return 0;
}